from typing import List


# 22. 括号生成
# 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
def generateParenthesis(n: int) -> List[str]:
    re = list()

    def back_track(left_count: int, right_count: int,
                   current_list: List[str], result_list: List[str]):
        # 左括号、右括号全部用尽的情况
        if left_count == 0 and right_count == 0:
            result_list.append(''.join(current_list))
            return
        # 左括号、右括号没有用尽

        # 左括号没有用尽
        if left_count > 0:
            current_list.append('(')
            left_count -= 1
            back_track(left_count, right_count, current_list, result_list)
            left_count += 1
            current_list.pop()

        # 右括号没有用尽
        if right_count > left_count:
            current_list.append(')')
            right_count -= 1
            back_track(left_count, right_count, current_list, result_list)
            right_count -= 1
            current_list.pop()

    back_track(n, n, [], re)

    return re


result = generateParenthesis(1)
print(f"result:{result}")

result = generateParenthesis(2)
print(f"result:{result}")

result = generateParenthesis(3)
print(f"result:{result}")
